package sorting;

import java.util.Arrays;

public class SortingUtils {

    private static int quickPivotTime = 0;
    private static int quickSwapTime = 0;

    /**
     * 冒泡算法
     */
    public static int[] bubble(int[] arr) {
        int time = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    time++;
                    swap(arr, j, j + 1, time);
                    printCurrentArr("冒泡排序", time, arr);
                }
            }
        }
        return arr;
    }

    /**
     * 选择排序
     */
    public static int[] select(int[] arr) {
        int length = arr.length;
        int time = 0;
        for (int i = 0; i < length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            time++;
            swap(arr, minIndex, i, time);
            printCurrentArr("选择排序", time, arr);
        }
        return arr;
    }

    /**
     * 插入排序
     */
    public static int[] insert(int[] arr) {
        int time = 0;
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int t = i - 1;
            while (t >= 0 && arr[t] > temp) {
                arr[t + 1] = arr[t];
                t--;
                time++;
                printCurrentArr("插入排序", time, arr);
            }
            arr[t + 1] = temp;
            time++;
            printCurrentArr("插入排序", time, arr);
        }
        return arr;
    }

    /**
     * 快速排序
     */
    public static int[] quick(int[] arr, int left, int right) {
        int i = left;
        int j = right;
        int middleIndex = (left + right) / 2;
        int pivot = arr[middleIndex];
        quickPivotTime++;
        printPivot(middleIndex, pivot, quickPivotTime);
        while (i <= j) {
            while (pivot > arr[i]) {
                i++;
            }
            while (pivot < arr[j]) {
                j--;
            }
            if (i <= j) {
                quickSwapTime++;
                swap(arr, i, j, quickSwapTime);
                printCurrentArr("快速排序", quickSwapTime, arr);
                i++;
                j--;
            }
            if (0 < j) {
                quick(arr, left, j);
            }
            if (i < arr.length - 1) {
                quick(arr, i, right);
            }
        }
        return arr;
    }

    private static void printPivot(int middleIndex, int pivot, int time) {
        System.out.println("第" + time + "次排序获取到的基准数为：arr[" + middleIndex + "]=" + pivot);
    }

    /**
     * 交换数组中的两个元素
     */
    private static void swap(int[] arr, int index1, int index2, int time) {
        System.out.println("第" + time + "次发生交换的元素是：" + "arr[" + index1 + "]=" + arr[index1] + "和arr[" + index2 + "]=" + arr[index2]);
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

    private static void printCurrentArr(String algorithm, int time, int[] arr) {
        System.out.println(algorithm + "算法第" + time + "次排序后结果：" + Arrays.toString(arr));
    }

}
